{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Decoding the DMPlex\n",
      "===================\n",
      "\n",
      "The purpose of this notebook is to provide a tutorial for the DMPlex features in PETSc. DMPlex and its sub-objects are an attempt to properly abstract out the concept of grids and the assignment of degree of freedom information to entities in that grid. The hope is that this will allow for easy implementation of different discretization ideas and subsequently lead to their fair comparison. To be able to use DMPlex you need to speak its language and understand how to get the information your methods need. In this tutorial I will explain and demonstrate the functionality of the DMPlex API."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import sys,petsc4py\n",
      "petsc4py.init(sys.argv)\n",
      "from petsc4py import PETSc\n",
      "import numpy as np"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "One way to create a DMPlex is to specify coordinates of vertices and cell connectivities. Here we encode a simple 2 by 2 element mesh of quads."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "dim = 2\n",
      "coords = np.asarray([[0.0, 0.0],\n",
      "                     [0.5, 0.0],\n",
      "                     [1.0, 0.0],\n",
      "                     [0.0, 0.5],\n",
      "                     [0.5, 0.5],\n",
      "                     [1.0, 0.5],\n",
      "                     [0.0, 1.0],\n",
      "                     [0.5, 1.0],\n",
      "                     [1.0, 1.0]])\n",
      "cells = np.asarray([[0,1,4,3],\n",
      "                    [1,2,5,4],\n",
      "                    [3,4,7,6],\n",
      "                    [4,5,8,7]],dtype='int32')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Now we initialize the DMPlex using this mesh information. "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plex = PETSc.DMPlex().createFromCellList(dim,cells,coords)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "PETSc converts the mesh into their abstraction of a topology which they store as a Hasse Diagram. Essentially this is a list of integers which encodes all the entities of each dimenion. We can use the view method to see what the DMPlex has encoded (broken, prints to the terminal but not here, capture magic doesn't work)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plex.view()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The view reveals that we have a mesh in 2 dimensions and that we have 9 0-cells (vertices), 12 1-cells (edges), and 4 2-cells (quads). All mesh entities are stored as integers in a single array called a chart. Each entity in the chart is called a point. (At this point it would be good to make some kind of plot with all points numbered, I suggest sketching one.)\n",
      "\n",
      "Cones and Supports\n",
      "------------------\n",
      "\n",
      "The *cone* of a point consists of the points of a dimension lower which make up that entity. So we can loop through the chart and print out each points' cone."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "pStart,pEnd = plex.getChart()\n",
      "for i in range(pStart,pEnd):\n",
      "    print \"point =\", i, \"\\tcone =\", plex.getCone(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "point = 0 \tcone = [13 14 15 16]\n",
        "point = 1 \tcone = [17 18 19 14]\n",
        "point = 2 \tcone = [15 20 21 22]\n",
        "point = 3 \tcone = [19 23 24 20]\n",
        "point = 4 \tcone = []\n",
        "point = 5 \tcone = []\n",
        "point = 6 \tcone = []\n",
        "point = 7 \tcone = []\n",
        "point = 8 \tcone = []\n",
        "point = 9 \tcone = []\n",
        "point = 10 \tcone = []\n",
        "point = 11 \tcone = []\n",
        "point = 12 \tcone = []\n",
        "point = 13 \tcone = [4 5]\n",
        "point = 14 \tcone = [5 8]\n",
        "point = 15 \tcone = [8 7]\n",
        "point = 16 \tcone = [7 4]\n",
        "point = 17 \tcone = [5 6]\n",
        "point = 18 \tcone = [6 9]\n",
        "point = 19 \tcone = [9 8]\n",
        "point = 20 \tcone = [ 8 11]\n",
        "point = 21 \tcone = [11 10]\n",
        "point = 22 \tcone = [10  7]\n",
        "point = 23 \tcone = [ 9 12]\n",
        "point = 24 \tcone = [12 11]\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Note that the numbering is completely different from our original mesh encoding. Here we summarize what we observe from the cones of the chart entities.\n",
      "\n",
      "* Points 0 through 3 correspond to quad cells. So their cones are made up of lists of 4 integers which refer to the lower dimensional entities which make up that cell--the edges. \n",
      "* Points 4 through 12 correspond to vertices. These are the lowest dimensional object we have and thus they are empty.\n",
      "* Points 13 through 24 correspond to edges. Each edge is made up of two vertices.\n",
      "\n",
      "Similarly, each point has a support. The *support* of a point is the list which consists of points of a higher dimension which contain the point in its cone. So we can now repeat the above exercise but for the support."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(pStart,pEnd):\n",
      "    print \"point =\", i, \"\\tsupport =\", plex.getSupport(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "point = 0 \tsupport = []\n",
        "point = 1 \tsupport = []\n",
        "point = 2 \tsupport = []\n",
        "point = 3 \tsupport = []\n",
        "point = 4 \tsupport = [13 16]\n",
        "point = 5 \tsupport = [13 14 17]\n",
        "point = 6 \tsupport = [17 18]\n",
        "point = 7 \tsupport = [15 16 22]\n",
        "point = 8 \tsupport = [14 15 19 20]\n",
        "point = 9 \tsupport = [18 19 23]\n",
        "point = 10 \tsupport = [21 22]\n",
        "point = 11 \tsupport = [20 21 24]\n",
        "point = 12 \tsupport = [23 24]\n",
        "point = 13 \tsupport = [0]\n",
        "point = 14 \tsupport = [0 1]\n",
        "point = 15 \tsupport = [0 2]\n",
        "point = 16 \tsupport = [0]\n",
        "point = 17 \tsupport = [1]\n",
        "point = 18 \tsupport = [1]\n",
        "point = 19 \tsupport = [1 3]\n",
        "point = 20 \tsupport = [2 3]\n",
        "point = 21 \tsupport = [2]\n",
        "point = 22 \tsupport = [2]\n",
        "point = 23 \tsupport = [3]\n",
        "point = 24 \tsupport = [3]\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "* Points 0 through 3 (quads) have no support, there is nothing of higher dimension in this mesh\n",
      "* Points 4 through 12 (vertices) have at least 2 edges in their support and the middle (8) has 4 edges\n",
      "* Points 13 through 24 (edges) have at least 1 cell in their support as many as 2\n",
      "\n",
      "So the DMPlex is a dimension-independent, low memory, abstract representation of a topology which we use to represent grid objects. The DMPlex knows nothing about elements, basis functions, fluxes, degrees of freedom, etc. It is just the topology itself and is completely general. DMPlex can be used to construct any kind of topological relation. Here we created one from a cell list and then accessed its cone/support information. A DMPlex can also be built by hand using the appropriate *set* routines or with other kinds of constructors available in the API.\n",
      "\n",
      "Labeling\n",
      "--------\n",
      "\n",
      "DMPlex provides support for the labeling of points. This can be helpful if you would like to flag certain entities for some reason. By default, the DMPlex comes with a label called 'depth'. This labels each entity based on how deep it is in the chart. You could also think of it as the dimensionality of the objects. Here we can check that the label does exist."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(plex.getNumLabels()):\n",
      "    name = plex.getLabelName(i)\n",
      "    print \"label name = %s\" % name, \"\\tlabel size = %d\" % plex.getLabelSize(name)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "label name = boundary \tlabel size = 1\n",
        "label name = depth \tlabel size = 3\n"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "So the label 'depth' does exist and we see that there are 3 different entries. Now we will loop over each item in the DMPlex and print the value of the label."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(pStart,pEnd):\n",
      "    print \"point =\",i, \"\\tlabel(depth) = %d\" % plex.getLabelValue(\"depth\",i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "point = 0 \tlabel(depth) = 2\n",
        "point = 1 \tlabel(depth) = 2\n",
        "point = 2 \tlabel(depth) = 2\n",
        "point = 3 \tlabel(depth) = 2\n",
        "point = 4 \tlabel(depth) = 0\n",
        "point = 5 \tlabel(depth) = 0\n",
        "point = 6 \tlabel(depth) = 0\n",
        "point = 7 \tlabel(depth) = 0\n",
        "point = 8 \tlabel(depth) = 0\n",
        "point = 9 \tlabel(depth) = 0\n",
        "point = 10 \tlabel(depth) = 0\n",
        "point = 11 \tlabel(depth) = 0\n",
        "point = 12 \tlabel(depth) = 0\n",
        "point = 13 \tlabel(depth) = 1\n",
        "point = 14 \tlabel(depth) = 1\n",
        "point = 15 \tlabel(depth) = 1\n",
        "point = 16 \tlabel(depth) = 1\n",
        "point = 17 \tlabel(depth) = 1\n",
        "point = 18 \tlabel(depth) = 1\n",
        "point = 19 \tlabel(depth) = 1\n",
        "point = 20 \tlabel(depth) = 1\n",
        "point = 21 \tlabel(depth) = 1\n",
        "point = 22 \tlabel(depth) = 1\n",
        "point = 23 \tlabel(depth) = 1\n",
        "point = 24 \tlabel(depth) = 1\n"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The depths listed match our intuition of which entities were which when we looked at the cones and support. The DMPlex has support for identifying the range of indices in the chart which correspond to each value of the depth, the so-called *depth stratum*. (I do not understand what height stratum is for yet)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(plex.getDepth()+1):\n",
      "    print \"depth = %d\" % i,\"\\tdepth stratum = \",plex.getDepthStratum(i),\"\\theight stratum = \",plex.getHeightStratum(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "depth = 0 \tdepth stratum =  (4, 13) \theight stratum =  (0, 4)\n",
        "depth = 1 \tdepth stratum =  (13, 25) \theight stratum =  (13, 25)\n",
        "depth = 2 \tdepth stratum =  (0, 4) \theight stratum =  (4, 13)\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can also use labels to mark, say, boundary edges. These are the edges with only 1 entry in the support."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "plex.createLabel(\"boundary\")\n",
      "for i in range(pStart,pEnd):\n",
      "    if plex.getLabelValue(\"depth\",i) == 1: # this is an edge\n",
      "        if plex.getSupportSize(i) == 1:    # only one cell has it as an edge\n",
      "            plex.setLabelValue(\"boundary\",i,1)\n",
      "    print \"point =\", i, \"\\tlabel(boundary) = %d\" % plex.getLabelValue(\"boundary\",i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "point = 0 \tlabel(boundary) = -1\n",
        "point = 1 \tlabel(boundary) = -1\n",
        "point = 2 \tlabel(boundary) = -1\n",
        "point = 3 \tlabel(boundary) = -1\n",
        "point = 4 \tlabel(boundary) = -1\n",
        "point = 5 \tlabel(boundary) = -1\n",
        "point = 6 \tlabel(boundary) = -1\n",
        "point = 7 \tlabel(boundary) = -1\n",
        "point = 8 \tlabel(boundary) = -1\n",
        "point = 9 \tlabel(boundary) = -1\n",
        "point = 10 \tlabel(boundary) = -1\n",
        "point = 11 \tlabel(boundary) = -1\n",
        "point = 12 \tlabel(boundary) = -1\n",
        "point = 13 \tlabel(boundary) = 1\n",
        "point = 14 \tlabel(boundary) = -1\n",
        "point = 15 \tlabel(boundary) = -1\n",
        "point = 16 \tlabel(boundary) = 1\n",
        "point = 17 \tlabel(boundary) = 1\n",
        "point = 18 \tlabel(boundary) = 1\n",
        "point = 19 \tlabel(boundary) = -1\n",
        "point = 20 \tlabel(boundary) = -1\n",
        "point = 21 \tlabel(boundary) = 1\n",
        "point = 22 \tlabel(boundary) = 1\n",
        "point = 23 \tlabel(boundary) = 1\n",
        "point = 24 \tlabel(boundary) = 1\n"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The default values are set to -1 and the boundary edges were marked with a 1. Labels aren't so useful on their own--the useful part about labeling things is that you can also get index sets of all entities with the same value of label. This means that if we wanted an index set which maps vertex numbers to the chartID we can get the PETSc IS for the 'depth' label for a value of 0 (again view doesn't print here)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "vis = plex.getStratumIS(\"depth\",0)\n",
      "vis.view()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Note that there are also routines which would appear to do the same as the above. However, their index sets return a local to global mapping of vertices (smallest depth in chart) and cells (largest depth in chart) useful in parallel."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "vis = plex.getVertexNumbering()\n",
      "vis.view()\n",
      "cis = plex.getCellNumbering()\n",
      "cis.view()"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Meets and Joins\n",
      "---------------\n",
      "\n",
      "Many times in performing grid operations, you need to know how lower and/or higher dimensional items are connected to each other. In the PETSc parlance, these are called *meets* and *joins*. A *meet* of a set of points is the intersection of the points' cones and a *join* is the intersection of the points' support. Here we demonstrate the concept with a few examples."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Two cells, meet is the common edge, no join\n",
      "pnts = [0,1]\n",
      "print \"meet =\",plex.getMeet(pnts),\"\\tjoin =\",plex.getJoin(pnts)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "meet = [14] \tjoin = []\n"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Two edges, meet is the common vertex, join is the cell to which they are both connected\n",
      "pnts = [14,19]\n",
      "print \"meet =\",plex.getMeet(pnts),\"\\tjoin =\",plex.getJoin(pnts)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "meet = [8] \tjoin = [1]\n"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Two vertices, no meet, join is the common edge to which they are both connected\n",
      "pnts = [8,11]\n",
      "print \"meet =\",plex.getMeet(pnts),\"\\tjoin =\",plex.getJoin(pnts)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "meet = [] \tjoin = [20]\n"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Transitive Closure\n",
      "------------------\n",
      "\n",
      "The transitive closure of a point in the DMPlex is a list of all reachable points from the given point, by default in the 'in-edge' direction. The transitive closure is then a set created by recursively taking the union on all points in the cone and its cones. In other words, it is all points of lower or equal dimension that this point can \"reach\". The routine also returns an array parallel to the closure array which defines how the points are oriented relative to the give point (e.g. for a cell, you might need to flip some edges to follow a right-handed convention). There is a flag in the routine, useCone, which if set to False will perform the same operation but in the 'out-edge' direction (that is, instead of recursively operating on cones, it will use the supports)."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for i in range(pStart,pEnd):\n",
      "    coneclose,orient = plex.getTransitiveClosure(i)\n",
      "    suppclose,orient = plex.getTransitiveClosure(i,useCone=False)\n",
      "    print \"point =\",i,\"\\tclosure(cone) =\",coneclose,\"\\tclosure(supp) =\",suppclose"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "point = 0 \tclosure(cone) = [ 0 13 14 15 16  4  5  8  7] \tclosure(supp) = [0]\n",
        "point = 1 \tclosure(cone) = [ 1 17 18 19 14  5  6  9  8] \tclosure(supp) = [1]\n",
        "point = 2 \tclosure(cone) = [ 2 15 20 21 22  7  8 11 10] \tclosure(supp) = [2]\n",
        "point = 3 \tclosure(cone) = [ 3 19 23 24 20  8  9 12 11] \tclosure(supp) = [3]\n",
        "point = 4 \tclosure(cone) = [4] \tclosure(supp) = [ 4 13 16  0]\n",
        "point = 5 \tclosure(cone) = [5] \tclosure(supp) = [ 5 13 14 17  0  1]\n",
        "point = 6 \tclosure(cone) = [6] \tclosure(supp) = [ 6 17 18  1]\n",
        "point = 7 \tclosure(cone) = [7] \tclosure(supp) = [ 7 15 16 22  0  2]\n",
        "point = 8 \tclosure(cone) = [8] \tclosure(supp) = [ 8 14 15 19 20  0  1  2  3]\n",
        "point = 9 \tclosure(cone) = [9] \tclosure(supp) = [ 9 18 19 23  1  3]\n",
        "point = 10 \tclosure(cone) = [10] \tclosure(supp) = [10 21 22  2]\n",
        "point = 11 \tclosure(cone) = [11] \tclosure(supp) = [11 20 21 24  2  3]\n",
        "point = 12 \tclosure(cone) = [12] \tclosure(supp) = [12 23 24  3]\n",
        "point = 13 \tclosure(cone) = [13  4  5] \tclosure(supp) = [13  0]\n",
        "point = 14 \tclosure(cone) = [14  5  8] \tclosure(supp) = [14  0  1]\n",
        "point = 15 \tclosure(cone) = [15  8  7] \tclosure(supp) = [15  0  2]\n",
        "point = 16 \tclosure(cone) = [16  7  4] \tclosure(supp) = [16  0]\n",
        "point = 17 \tclosure(cone) = [17  5  6] \tclosure(supp) = [17  1]\n",
        "point = 18 \tclosure(cone) = [18  6  9] \tclosure(supp) = [18  1]\n",
        "point = 19 \tclosure(cone) = [19  9  8] \tclosure(supp) = [19  1  3]\n",
        "point = 20 \tclosure(cone) = [20  8 11] \tclosure(supp) = [20  2  3]\n",
        "point = 21 \tclosure(cone) = [21 11 10] \tclosure(supp) = [21  2]\n",
        "point = 22 \tclosure(cone) = [22 10  7] \tclosure(supp) = [22  2]\n",
        "point = 23 \tclosure(cone) = [23  9 12] \tclosure(supp) = [23  3]\n",
        "point = 24 \tclosure(cone) = [24 12 11] \tclosure(supp) = [24  3]\n"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    }
   ],
   "metadata": {}
  }
 ]
}